import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.Iterator;
import java.util.ListIterator;

public class Helper {

	public static boolean isItADeadlock(Board board, PlayerNBoxes pnb, Position boxToTest){

	
//		System.out.println("isItADeadlock called, test: ");
//		System.out.println(board);
//		System.out.println(pnb);
		
		Position box = boxToTest;
		
//		for ( Position box : pnb.getBoxes()){
			int i=box.getI();
			int j=box.getJ();
			if (board.getData(i, j) == Board.GOAL  ){
//				continue;
				return false;
			}

			// check if it is possible to reach the box from to sides in at least one direction
			if (	(	   	( board.getData(i-1, j) == Board.EMPTY || board.getData(i-1, j) == Board.GOAL ) && 	// if its empty above
						   	( board.getData(i+1, j) == Board.EMPTY || board.getData(i+1, j) == Board.GOAL )		// if its empty below		
					) || ( 	( board.getData(i, j-1) == Board.EMPTY || board.getData(i, j-1) == Board.GOAL ) && 	// if its empty to left
							( board.getData(i, j+1) == Board.EMPTY || board.getData(i, j+1) == Board.GOAL )		// if its empty to right 
						 ) 
					)
			{// do nothing
			}else{
				return true;
			}

			// alloc temp variables
			byte above = Board.EMPTY;
			byte below = Board.EMPTY;
			byte toLeft = Board.EMPTY;
			byte toRight = Board.EMPTY;
			
			// set temp variables
			if ( board.getData(i-1, j) == Board.WALL){		above   = Board.WALL;		}
			if ( board.getData(i+1, j) == Board.WALL){		below   = Board.WALL;		}
			if ( board.getData(i, j-1) == Board.WALL){		toLeft  = Board.WALL;		}
			if ( board.getData(i, j+1) == Board.WALL){		toRight = Board.WALL;		}
			
			
			// check boxes relations 
			// if box found above
			if ( getBoxAt(i-1, j, pnb.getBoxes()) != null ){
				// if box is not horizontal movable 
				if ( (toLeft != Board.EMPTY || toRight != Board.EMPTY) && (board.getData(i-1, j-1) == Board.WALL || board.getData(i-1, j+1) == Board.WALL)){
					return true;
				}
			}
			// if box found below
			if ( getBoxAt(i+1, j, pnb.getBoxes()) != null ){
				// if box is not horizontal movable 
				if ( (toLeft != Board.EMPTY || toRight != Board.EMPTY ) && (board.getData(i+1, j-1) == Board.WALL || board.getData(i+1, j+1) == Board.WALL)){
					return true;
				}
			}
			
			// if box found left
			if ( getBoxAt(i, j-1, pnb.getBoxes()) != null ){
				// if box is not vertical movable 
				if ( (above != Board.EMPTY || below != Board.EMPTY) && (board.getData(i-1, j-1) == Board.WALL || board.getData(i+1, j-1) == Board.WALL)){
					return true;
				}
			}
			// if box found right
			if ( getBoxAt(i, j+1, pnb.getBoxes()) != null ){
				// if box is not vertical movable 
				if ( ( above != Board.EMPTY || below != Board.EMPTY ) && (board.getData(i-1, j+1) == Board.WALL || board.getData(i+1, j+1) == Board.WALL)){
					return true;
				}
			}
			
			if ( getBoxAt(i, j+1, pnb.getBoxes()) != null &&  getBoxAt(i+1, j+1, pnb.getBoxes()) != null && getBoxAt(i+1, j, pnb.getBoxes()) != null ){
				return true;
			}
			if ( getBoxAt(i, j-1, pnb.getBoxes()) != null &&  getBoxAt(i+1, j-1, pnb.getBoxes()) != null && getBoxAt(i+1, j, pnb.getBoxes()) != null ){
				return true;
			}
			if ( getBoxAt(i-1, j, pnb.getBoxes()) != null &&  getBoxAt(i-1, j+1, pnb.getBoxes()) != null && getBoxAt(i, j+1, pnb.getBoxes()) != null ){
				return true;
			}
			if ( getBoxAt(i, j-1, pnb.getBoxes()) != null &&  getBoxAt(i-1, j-1, pnb.getBoxes()) != null && getBoxAt(i-1, j, pnb.getBoxes()) != null ){
				return true;
			}
			
			// check if we can get the box back from a wall

			// wall above
			if ( above == Board.WALL ){
				int nextWallToLeft = -1;
				int nextWallToRight = -1;
				for ( int cj = 0; cj < board.getNumColumns(); cj++){
					if ( board.getData(i, cj)  == Board.WALL){
						if ( cj < j && cj > nextWallToLeft  ){		nextWallToLeft = cj;			}
						if ( cj > j && cj > nextWallToLeft  ){		nextWallToRight = cj;	break;	}
					}
				}
				boolean isDeadLock =  true;
				for ( int cj = nextWallToLeft+1 ; cj < nextWallToRight; cj++){
					if ( board.getData(i-1, cj)  == Board.EMPTY /*&& board.getData(i-1, cj+1) == Board.EMPTY*/ 
							|| board.getData(i, cj) == Board.GOAL
							|| board.getData(i-1, cj) == Board.GOAL){
						isDeadLock = false;
						break;
					}
				}
				if ( isDeadLock){ 	return true;	}
			}
			
			// wall below
			if ( below == Board.WALL ){
				int nextWallToLeft = -1;
				int nextWallToRight = -1;
				for ( int cj = 0; cj < board.getNumColumns(); cj++){
					if ( board.getData(i, cj)  == Board.WALL){
						if ( cj < j && cj > nextWallToLeft  ){		nextWallToLeft = cj;			}
						if ( cj > j && cj > nextWallToLeft  ){		nextWallToRight = cj;	break;	}
					}
				}
				boolean isDeadLock =  true;
				for ( int cj = nextWallToLeft+1 ; cj < nextWallToRight; cj++){
					if ( board.getData(i+1, cj)  == Board.EMPTY /*&& board.getData(i+1, cj+1) == Board.EMPTY */
							|| board.getData(i, cj) == Board.GOAL
							|| board.getData(i+1, cj) == Board.GOAL){
						isDeadLock = false;
						break;
					}
				}
				if ( isDeadLock){	return true;	}
			}
			
			// wall left
			if ( toLeft == Board.WALL ){
				int nextWallToTop= -1;
				int nextWallToBelow = -1;
				for ( int ri = 0; ri < board.getNumRows(); ri++){
					if ( board.getData(ri, j)  == Board.WALL){
						if ( ri < i && ri > nextWallToTop ){		nextWallToTop = ri;				}
						if ( ri > i && ri > nextWallToBelow  ){		nextWallToBelow = ri;	break;	}
					}
				}
				boolean isDeadLock =  true;
				for ( int ri = nextWallToTop+1 ; ri < nextWallToBelow; ri++){
					if ( board.getData(ri, j-1)  == Board.EMPTY /*&& board.getData(ri+1, j-1) == Board.EMPTY*/ 
							|| board.getData(ri, j) == Board.GOAL
							|| board.getData(ri, j-1) == Board.GOAL){
						isDeadLock = false;
						break;
					}
				}
				if ( isDeadLock){	return true;	}
			}
			
			// wall right
			if ( toRight == Board.WALL ){
				int nextWallToTop= -1;
				int nextWallToBelow = -1;
				for ( int ri = 0; ri < board.getNumRows(); ri++){
					if ( board.getData(ri, j)  == Board.WALL){
						if ( ri < i && ri > nextWallToTop ){		nextWallToTop = ri;				}
						if ( ri > i && ri > nextWallToBelow  ){		nextWallToBelow = ri;	break;	}
					}
				}
				boolean isDeadLock =  true;
				for ( int ri = nextWallToTop+1 ; ri < nextWallToBelow; ri++){
					if ( board.getData(ri, j+1)  == Board.EMPTY /*&& board.getData(ri+1, j+1) == Board.EMPTY */
							|| board.getData(ri, j) == Board.GOAL
							|| board.getData(ri, j+1) == Board.GOAL){
						isDeadLock = false;
						break;
					}
				}
				if ( isDeadLock){	return true;	}
			}
			
			
			
//		}
		return false;
	}
	
	/********************************************************************************************/
	
	private static Position getBoxAt(int i, int j, Position[] boxes){
		for ( Position pos : boxes){
			if ( pos.getI() == i && pos.getJ() == j){
				return pos;
			}
		}
		return null;
	}
	
	public static byte[][] joinBoards(Board board, PlayerNBoxes pnb){
		byte[][] jointedBoard = new byte[board.getNumRows()][board.getNumColumns()];
		for ( int i = 0; i < board.getNumRows(); i++){
			for ( int j = 0; j <  board.getNumColumns(); j++){
				jointedBoard[i][j] = board.getData(i, j);
			}
		}
		for (Position pos : pnb.getBoxes()){
			jointedBoard[pos.getI()][pos.getJ()] |= Board.BOX;
		}
		jointedBoard[pnb.getPlayer().getI()][pnb.getPlayer().getJ()] |= Board.PLAYER;
		return jointedBoard;
	}
	
//	
	
	public static PlayerNBoxes doMove( PlayerNBoxes pnb, Position newPos){
		Position boxToMove = getBoxAt(newPos.getI(), newPos.getJ(), pnb.getBoxes());
		PlayerNBoxes re =new PlayerNBoxes(newPos, pnb.getBoxes());
		if ( boxToMove != null){
			byte direction = getDirection(pnb, newPos);
			if ( direction == Move.MOVE_UP){
				re.moveBox(boxToMove, new Position(boxToMove.getI()-1,boxToMove.getJ()));
			}else if ( direction == Move.MOVE_DOWN){
				re.moveBox(boxToMove, new Position(boxToMove.getI()+1,boxToMove.getJ()));
			}else if ( direction == Move.MOVE_LEFT){
				re.moveBox(boxToMove, new Position(boxToMove.getI(),boxToMove.getJ()-1));
			}else if ( direction == Move.MOVE_RIGHT){
				re.moveBox(boxToMove, new Position(boxToMove.getI(),boxToMove.getJ()+1));
			}
		}
		return re;
	}
	
	public static byte getDirection(PlayerNBoxes start, Position end){
		if ( start.getPlayer().getI() > end.getI()){
			return Move.MOVE_UP;
		}
		if ( start.getPlayer().getI() < end.getI()){
			return Move.MOVE_DOWN;
		}
		if ( start.getPlayer().getJ() > end.getJ()){
			return Move.MOVE_LEFT;
		}
		if ( start.getPlayer().getJ() < end.getJ()){
			return Move.MOVE_RIGHT;
		}
		return -1;
	}
	
	public static String getDirection(PlayerNBoxes start, PlayerNBoxes end){
		if ( start.getPlayer().getI() > end.getPlayer().getI()){
			return "U";
		}
		if ( start.getPlayer().getI() < end.getPlayer().getI()){
			return "D";
		}
		if ( start.getPlayer().getJ() > end.getPlayer().getJ()){
			return "L";
		}
		if ( start.getPlayer().getJ() < end.getPlayer().getJ()){
			return "R";
		}
		return "";
	}
	
	public static void printjoint(byte[][] mat){
		System.out.println(Board.toString(mat, mat.length, mat[0].length));
	}
	
	public static ArrayList<Position> findFreeGoals(Board board, PlayerNBoxes pnb){
		ArrayList<Position> Goals = new ArrayList<Position>();
		for (int k=0; k<board.getNumRows(); k++){
			for (int l=0; l<board.getNumColumns(); l++){
				if ((board.getData(k,l)&Board.GOAL) !=0 && !pnb.contains(k,l))
					Goals.add(new Position(k,l));					
			}
		}
		return Goals;
	}
	
	public static ArrayList<Move> possibleMoveBox(Board b, PlayerNBoxes pnb) {
		ArrayList<Move> tab = new ArrayList<Move>();
		int i=0;
		int bestScore=100;
		while(i<pnb.getBoxes().length){
			Position p = pnb.getBoxes()[i];
			// move left or right
			if ((b.getData(p.getI(),p.getJ()+1)&Board.WALL)==0
					&& pnb.getBoxAt(p.getI(),p.getJ()+1)==null
					&& (b.getData(p.getI(),p.getJ()-1)&Board.WALL)==0
					&& pnb.getBoxAt(p.getI(),p.getJ()-1)==null){
			
				if (PathFinding.isPathTo(new Position(p.getI(),p.getJ()-1),pnb, b)){
					tab.add(new Move(p,Move.MOVE_RIGHT));
				}

				if (PathFinding.isPathTo(new Position(p.getI(),p.getJ()+1), pnb, b)){
					tab.add(new Move(p,Move.MOVE_LEFT));
				}
			}
			
			// move up or down
			if ((b.getData(p.getI()+1,p.getJ())&Board.WALL)==0
					&& pnb.getBoxAt(p.getI()+1,p.getJ())==null
					&& (b.getData(p.getI()-1,p.getJ())&Board.WALL)==0
					&& pnb.getBoxAt(p.getI()-1,p.getJ())==null){
				if (PathFinding.isPathTo(new Position(p.getI()-1,p.getJ()), pnb, b)){
					tab.add(new Move(p,Move.MOVE_DOWN));
				}
				if (PathFinding.isPathTo(new Position(p.getI()+1,p.getJ()), pnb, b)){
					tab.add(new Move(p,Move.MOVE_UP));
				}
			}
			i++;
		}
		
		return tab;
	}

	public static PlayerNBoxes boxMove(PlayerNBoxes pnb, Move m) {
		PlayerNBoxes ans = new PlayerNBoxes(pnb);
		ans.moveBox(m.getStart(), m.getEnd());
		ans.setPlayer(m.getStart());
		return ans;
	}

	/** compute the way for the man once we know the way of all the boxes.
	 * @return solution the string to be return to the server
	 */
	public static String manWay(Board b, PlayerNBoxes pnb, ArrayList<Move> array){
		ListIterator<Move> itr = array.listIterator(array.size());
		String solution = "";
		Position target, targetBox;
		String oneWay;
		while(itr.hasPrevious()) {
			Move actualMove = itr.previous();
			//Find the target square
			targetBox = new Position(actualMove.getStart());
			if (actualMove.getDirection() == Move.MOVE_UP)
				target = new Position(targetBox.getI()+1,targetBox.getJ());
			else if (actualMove.getDirection() == Move.MOVE_DOWN)
				target = new Position(targetBox.getI()-1,targetBox.getJ());
			else if (actualMove.getDirection() == Move.MOVE_LEFT)
				target = new Position(targetBox.getI(),targetBox.getJ()+1);
			else
				target = new Position(targetBox.getI(),targetBox.getJ()-1);
			
			
			oneWay = PathFinding.pathTo(target, pnb, b);
			pnb = Helper.boxMove(pnb, actualMove);
//			oneWay = PathFinding.pathTo(target, pnb, b);
			
			if (actualMove.getDirection() == Move.MOVE_UP)
				solution += oneWay+"U";
			else if (actualMove.getDirection() == Move.MOVE_DOWN)
				solution += oneWay+"D";
			else if (actualMove.getDirection() == Move.MOVE_LEFT)
				solution += oneWay+"L";
			else
				solution += oneWay+"R";
		}
		
		return solution;
	}
	
	public static ArrayList<Move> rankListOfMove(ArrayList<Move> moves, int[][] rankArray, PlayerNBoxes pnb, Board b) throws CloneNotSupportedException{
		ArrayList<Move> end = (ArrayList<Move>) moves.clone();
		
		ListCompare c = new ListCompare(rankArray, pnb, b );		
		Collections.sort(end, c);
//		
//		for(int i=0; i<end.size();i++){
//			System.out.println(end.get(i).toString());
//			PlayerNBoxes p = pnb.move(end.get(i));
//			p.setRank(b);
//			int ranki = p.getRank();
//			System.out.println(ranki);
//		}		
//		
				
		
		return end;
	}
	
	
//	public static ArrayList<Position> getPossibleMoves( Board board, PlayerNBoxes pnb){
//		ArrayList<Position> re = new ArrayList<Position>();
//		
//		byte[][] jointedBoard = joinBoards(board, pnb);
//		
//		// check up == box
//		if (jointedBoard[ pnb.getPlayer().getI()-1][pnb.getPlayer().getJ()]== ( Board.BOX | Board.EMPTY ) || jointedBoard[ pnb.getPlayer().getI()-1][pnb.getPlayer().getJ()]== ( Board.BOX | Board.GOAL )){
//			if ( jointedBoard[ pnb.getPlayer().getI()-2][pnb.getPlayer().getJ()]== Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()-2][pnb.getPlayer().getJ()]== Board.GOAL ){
//				// search the right box
//				for ( Position pos : pnb.getBoxes()){
//					if ( pos.getI() == pnb.getPlayer().getI()-1 && pos.getJ() == pnb.getPlayer().getJ() ){
//						PlayerNBoxes tmp = doMove(pnb, new Position( pnb.getPlayer().getI()-1,pnb.getPlayer().getJ())); 
//						// if it is not a deadlock
//						if ( isItADeadlock(board, tmp) != true){
//							re.add(new Position(pnb.getPlayer().getI()-1, pnb.getPlayer().getJ()));
//						}
//						
//					}
//				}
//			}
//		}
//		// check down == box
//		if (jointedBoard[pnb.getPlayer().getI()+1][pnb.getPlayer().getJ()] == (Board.BOX | Board.EMPTY) || jointedBoard[pnb.getPlayer().getI()+1][pnb.getPlayer().getJ()] == (Board.BOX | Board.GOAL)){
//			if ( jointedBoard[ pnb.getPlayer().getI()+2][pnb.getPlayer().getJ()]== Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()+2][pnb.getPlayer().getJ()]== Board.GOAL ){
//				// search the right box
//				for ( Position pos : pnb.getBoxes()){
//					if ( pos.getI() == pnb.getPlayer().getI()+1 && pos.getJ() == pnb.getPlayer().getJ() ){
//						PlayerNBoxes tmp = doMove(pnb, new Position( pnb.getPlayer().getI()+1,pnb.getPlayer().getJ())); 
//						// if it is not a deadlock
//						if ( isItADeadlock(board, tmp) != true){
//							re.add(new Position(pnb.getPlayer().getI()+1, pnb.getPlayer().getJ()));
//						}
//					}
//				}
//			}
//		}
//		// check left == box
//		if (jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-1] == ( Board.BOX | Board.EMPTY) || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-1] == ( Board.BOX | Board.GOAL)){
//			if ( jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-2]== Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-2]== Board.GOAL  ){
//				// search the right box
//				for ( Position pos : pnb.getBoxes()){
//					if ( pos.getI() == pnb.getPlayer().getI() && pos.getJ() == pnb.getPlayer().getJ()-1){
//						PlayerNBoxes tmp = doMove(pnb, new Position( pnb.getPlayer().getI(),pnb.getPlayer().getJ()-1)); 
//						// if it is not a deadlock
//						if ( isItADeadlock(board, tmp) != true){
//							re.add(new Position(pnb.getPlayer().getI(), pnb.getPlayer().getJ()-1));
//						}
//					}
//				}
//			}
//		}
//		// check right == box
//		if (jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+1] == ( Board.BOX | Board.EMPTY) || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+1] == ( Board.BOX | Board.GOAL)){
//			if ( jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+2] == Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+2] == Board.GOAL){
//				// search the right box
//				for ( Position pos : pnb.getBoxes()){
//					if ( pos.getI() == pnb.getPlayer().getI() && pos.getJ() == pnb.getPlayer().getJ()+1 ){
//						PlayerNBoxes tmp = doMove(pnb, new Position( pnb.getPlayer().getI(),pnb.getPlayer().getJ()+1)); 
//						// if it is not a deadlock
//						if ( isItADeadlock(board, tmp) != true){
//							re.add(new Position(pnb.getPlayer().getI(), pnb.getPlayer().getJ()+1));
//						}
//					}
//				}
//			}
//		}
//		
//		// check up == free
//		if (jointedBoard[ pnb.getPlayer().getI()-1][pnb.getPlayer().getJ()]== Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()-1][pnb.getPlayer().getJ()]== Board.GOAL  ){
//			re.add(new Position(pnb.getPlayer().getI()-1, pnb.getPlayer().getJ()));
//		}
//		// check down == free
//		if (jointedBoard[pnb.getPlayer().getI()+1][pnb.getPlayer().getJ()] == Board.EMPTY || jointedBoard[pnb.getPlayer().getI()+1][pnb.getPlayer().getJ()] == Board.GOAL){
//			re.add(new Position(pnb.getPlayer().getI()+1,pnb.getPlayer().getJ()));
//		}
//		// check left == free
//		if (jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-1] == Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()-1] == Board.GOAL){
//			re.add(new Position(pnb.getPlayer().getI(),pnb.getPlayer().getJ()-1));
//		}
//		// check right == free
//		if (jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+1] == Board.EMPTY || jointedBoard[ pnb.getPlayer().getI()][pnb.getPlayer().getJ()+1] == Board.GOAL ){
//			re.add(new Position(pnb.getPlayer().getI(),pnb.getPlayer().getJ()+1));
//		}
//		
//		return re;
//	}
	
}
